package graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph {
	private ArrayList<String> vertexList;
	private int[][] edges;
	private int numOfEdges;
//	定义数组记录布尔值，标记节点遍历是否访问过
	private boolean[] visited;

	public static void main(String[] args) {
		// 图数据
		int[][] oxy = { { 0, 1 }, { 0, 2 }, { 1, 2 }, { 1, 3 }, { 1, 4 }, };
		int[][] xys = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 1, 4 }, { 3, 7 }, { 4, 7 }, { 2, 5 }, { 2, 6 }, { 5, 6 } };

		int n = xys.length; // 节点的个数
		// 创建图对象
		Graph graph = new Graph(n);

		String vertexs[] = graph.MapToChar(8, true);
		// 循环添加节点
		for (String value : vertexs) {
			graph.insertVertex(value);
		}
		// 添加边
		// 批量添加数据
		// A-B A-C B-C B-D B-E
//		graph.insertBatch(oxy);
		graph.insertBatch(xys);

		// 显示临界矩阵
		graph.showGraph();

		// 深度优先遍历
		graph.dfs();

		// 广度优先遍历
		graph.bfs();
	}

	Graph(int n) {
		edges = new int[n][n];
		vertexList = new ArrayList<>();
		numOfEdges = 0;
		visited = new boolean[n];
	}

	// 插入节点
	void insertVertex(String vertex) {
		vertexList.add(vertex);
	}

	/**
	 * 添加边
	 * 
	 * @param v1    表示点的下标即第几个顶点 "A" - "B" "A" -> 0 "B" -> 1
	 * @param v2    第二个顶点对应的下标
	 * @param weigh 权值，存在1，不存在0
	 */
	void insertEdge(int v1, int v2, int weigh) {
		edges[v1][v2] = weigh;
		edges[v2][v1] = weigh;
		numOfEdges++;
	}

	void insertBatch(int[][] xys) {
		for (int[] xy : xys) {
			insertEdge(xy[0], xy[1], 1);
		}
	}

	int getNumOfVertex() {
		return vertexList.size();
	}

	int getNumOfEdges() {
		return numOfEdges;
	}

	// 返回节点下标对应的数据
	String getValueIdx(int i) {
		return vertexList.get(i);
	}

	// 返回权值
	int getWeigh(int v1, int v2) {
		return edges[v1][v2];
	}

	/**
	 * 显示图对应的矩阵
	 */
	void showGraph() {
		for (int[] link : edges) {
			System.err.println(Arrays.toString(link));
		}
	}

	/**
	 * 得到第一个邻接节点的下标
	 * 
	 * @param idx
	 * @return 存在返回下标，否则-1
	 */
	int getFirstAdjacent(int idx) {
		for (int i = 0; i < vertexList.size(); i++) {
			if (edges[idx][i] > 0) {
				return i;
			}
		}
		return -1;
	}

	// 根据前一个邻接节点的下标获取下一个邻接节点
	int getNextAdjacent(int v1, int v2) {
		for (int i = v2 + 1; i < vertexList.size(); i++) {
			if (edges[v1][i] > 0) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 重载dfs,用于回溯
	 */
	void dfs() {
		System.out.println("dfs");
		// 遍历所有的节点，进行回溯
		for (int i = 0; i < getNumOfVertex(); i++) {
			if (!visited[i]) {
				dfs(visited, i);
			}
		}
		System.out.println();
		// 重置已访问标记，以进行再一次的广度或深度遍历
		visited = new boolean[visited.length];
	}

	/**
	 * 深度优先遍历算法 index初始为0
	 * 
	 * @param visited 是否访问
	 * @param index   下标
	 */
	void dfs(boolean[] visited, int index) {
		System.out.print(getValueIdx(index) + "->");
		// 节点置为已经访问
		visited[index] = true;
		// 获取一个节点的邻接节点
		int i = getFirstAdjacent(index);
		while (i != -1) {
			// i下标值没有被访问过
			if (!visited[i]) {
				dfs(visited, i);
			}
			// 如果i下标值访问过
			i = getNextAdjacent(index, i);
		}
	}

	void bfs() {
		System.out.println("bfs");
		for (int i = 0; i < getNumOfVertex(); i++) {
			if (!visited[i]) {
				bfs(visited, i);
			}
		}
		System.out.println();
		// 重置已访问标记，以进行再一次的广度或深度遍历
		visited = new boolean[visited.length];
	}

	/**
	 * 广度优先遍历算法 index初始为0
	 * 
	 * @param visited
	 * @param index
	 */
	void bfs(boolean[] visited, int index) {
		int head; // 队列头节点下标
		int i; // 邻接节点下标
		// 队列：节点访问的顺序
		LinkedList<Integer> list = new LinkedList<>();
		// 访问节点
		System.out.print(getValueIdx(index) + "->");
		// 标记为已访问
		visited[index] = true;
		// 加入队列
		list.addLast(index);

		while (!list.isEmpty()) {
			// 队列头节点下标
			head = list.removeFirst();
			i = getFirstAdjacent(head);
			while (i != -1) {
				if (!visited[i]) {
					System.out.print(getValueIdx(i) + "->");
					visited[i] = true;
					// 入队
					list.addLast(i);
				}
				// 以head为前驱，找i的下一个临界点
				i = getNextAdjacent(head, i);
			}
		}
	}

	/**
	 * 生成可输出的映射列表，供遍历参考
	 * 
	 * @param size
	 * @param isNum
	 * @return
	 */
	String[] MapToChar(int size, boolean isNum) {
		String[] s = new String[size];
		char a = 'A';
		char one = '1';
		for (int i = 0; i < s.length; i++) {
			s[i] = (isNum ? one++ : a++) + "";
		}
		return s;
	}
}
